package lhz.algorithm.chapter.two;

/**
 * 《算法导论》，习题2.3-7 
 * Describe a Θ(n lg n)-time algorithm that, given a set S of n
 * integers and another integer x, determines whether or not there exist two
 * elements in S whose sum is exactly x.
 * @author lihzh
 */
public class Excercise237 {

	private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };
	private static int sum = 11;

	public static void main(String[] args) {
		// 先利用合并排序，将给定数组排好序
		mergeSort(input);// 复杂度：Θ(nlgn)
		boolean isExist = false;
		// 设置循环结束位，每次找到符合条件的元素后，改变循环结束条件
		// 否则会出现11 = 1 + 10，11 = 10 + 1的重复情况。
		int end = input.length;
		for (int i = 0; i < end; i++) {// 复杂度：Θ(n)
			int temp = sum - input[i];
			// 利用二分查找，查询temp是否在数组中。
			Integer index = binarySearch(input, temp, 0, input.length - 1);// 复杂度：Θ(lgn)
			if (index != null && index != i) {// 不等于本身
				System.out.println(sum + " = " + input[i] + " + " + temp);
				end = index;
				isExist = true;
			}
		}
		if (!isExist) {
			System.out.println("数组不存在两个数的和为：" + sum);
		}
		/*
		 * 复杂度分析： 由注释可见，复杂度为：Θ(nlgn)
		 */
	}

	/**
	 * 合并排序，复杂度：Θ(nlgn)
	 * 
	 * @param array
	 * @return
	 */
	private static int[] mergeSort(int[] array) {
		// 如果数组的长度大于1，继续分解数组
		if (array.length > 1) {
			int leftLength = array.length / 2;
			int rightLength = array.length - leftLength;
			// 创建两个新的数组
			int[] left = new int[leftLength];
			int[] right = new int[rightLength];
			// 将array中的值分别对应复制到两个子数组中
			for (int i = 0; i < leftLength; i++) {
				left[i] = array[i];
			}
			for (int i = 0; i < rightLength; i++) {
				right[i] = array[leftLength + i];
			}
			// 递归利用合并排序，排序子数组
			left = mergeSort(left);
			right = mergeSort(right);
			// 设置初始索引
			int i = 0;
			int j = 0;
			for (int k = 0; k < array.length; k++) {
				// 如果左边数据索引到达边界则取右边的值
				if (i == leftLength && j < rightLength) {
					array[k] = right[j];
					j++;
					// 如果右边数组索引到达边界，取左数组的值
				} else if (i < leftLength && j == rightLength) {
					array[k] = left[i];
					i++;
					// 如果均为到达则取，较小的值
				} else if (i < leftLength && j < rightLength) {
					if (left[i] > right[j]) {
						array[k] = right[j];
						j++;
					} else {
						array[k] = left[i];
						i++;
					}
				}
			}
		}
		return array;
	}

	/**
	 * 二分查找，复杂度Θ(lg n)
	 * 
	 * @param input
	 * @param target
	 * @param from
	 * @param to
	 * @return
	 */
	private static Integer binarySearch(int[] input, int target, int from,
			int to) {
		int range = to - from;
		// 如果范围大于0，即存在两个以上的元素，则继续拆分
		if (range > 0) {
			// 选定中间位
			int mid = (to + from) / 2;
			// 先判断两个二分的临界位
			if (input[mid] == target) {
				return mid;
			}
			// 如果临界位不满足，则继续二分查找
			if (input[mid] > target) {
				return binarySearch(input, target, from, mid - 1);
			} else {
				return binarySearch(input, target, mid + 1, to);
			}
		} else {
			if (input[from] == target) {
				return from;
			} else {
				return null;
			}
		}
	}
}
